package LeetCode1;

/**
 * 排序链表
 *
 * @author 是阿秋啊
 * @date 2022/03/26 18:14
 **/
public class Num148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 找到链表的中间节点进行分割
        // 此处不能需要定义fast为head的下一结点
        // 因为low的下一节点要指向右侧的第一个结点
        ListNode low = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
        }
        // 归过程
        // temp替代右侧头节点
        ListNode temp = low.next;
        // 这里需要将low后边置空，不置空则会在left递归中陷入死循环
        low.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(temp);
        ListNode dummyHead = new ListNode(-50001);
        ListNode prev = dummyHead;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                prev.next = left;
                left = left.next;
            } else {
                prev.next = right;
                right = right.next;
            }
            prev = prev.next;
        }
        // 此时left或right有一个必然走空
        // 将未空的一边连上
        prev.next = left != null ? left : right;
        return dummyHead.next;
    }
}
